﻿using System;
using System.Collections.Generic;
using System.Text;

namespace NthTribonacciNumber
{
    public class Solution
    {
        private Dictionary<int, int> tribonacci = new Dictionary<int, int>() { { 0, 0 }, { 1, 1 }, { 2, 1 } };
        public int Tribonacci(int n)
        {
            if (tribonacci.ContainsKey(n))
            {
                return tribonacci[n];
            }
            else
            {
                var tri = Tribonacci(n - 1) + Tribonacci(n - 2) + Tribonacci(n - 3);
                tribonacci.Add(n, tri);
                return tri;
            }
        }
    }
}
